А.А. Викентьев, Л.Н. Коренева

1. Введение расстояний и его свойства

Зафиксируем язык первого порядка , состоящий из конечного числа предикатных символов. Пусть - непустое множество (элементы которого суть наблюдаемые объекты) мощности .

Имеется конечное число экспертов. Каждый эксперт дает свою интерпретацию символам языка в соответствующие частичные отношения (предикаты) на множестве . Это позволяет говорить о моделях.

Обозначим через множество всех моделей языка , определенных на множестве экспертами. Предположим, что на формульных подмножествах множества задана вероятностная мера .

Вместо частично заданного экспертом предиката будем рассматривать индуцированный предикат , который совпадает с на множестве точно определенных значений.

Введем расстояние между высказываниями (предикатами) на множестве частично заданных моделей . Модели различаются интерпретациями.

Определим расстояние между формульными подмножествами (предикатами) в каждой модели .

Определение1. Расстоянием между предикатами и , частично определенными в модели , назовем величину



Замечание. Если рассматриваемые предикаты имеют разную арность, т.е. эксперт не высказывается о значении некоторой характеристики, тогда полагаем, что эта характеристика является пустым множеством.

Расстояние между предикатами на всем семействе моделей определим как среднее на множестве расстояний в моделях.

Определение2. Расстоянием между предикатами и , частично определенными на множестве , назовем величину



Далее, для простоты обозначений, знак будем опускать, поскольку это не вызовет недоразумений.

Теперь рассмотрим способ определения расстояния между предложениями.

Обозначим через множество моделей из , на которых истинно предложение , т.е. ? .

Очевидно, существуют такие модели, на которых не тавтологичное предложение истинно, и такие, на которых оно ложно. Естественно измерять различие информации, содержащейся в предложениях, количеством моделей, на которых предложения принимают разные значения истинности.

Определение3. Расстоянием между предложениями и назовем величину



Рассмотрим еще один способ определения расстояния между формулами. Дополним язык первого порядка константами из множества . Для этого множества рассмотрим произвольные кортежи длины местности формул, равной .

При подстановке кортежей в формулы, в предположении, что формулы имеют одинаковую местность (как этого добиться, было показано выше), формулы становятся предложениями.

Определение4. Расстоянием между формулами и назовем величину

.

Доказана теорема, из которой следует, что предложенные расстояния действительно являются метриками. В теореме доказаны и некоторые дополнительные свойства введенных расстояний.

Теорема1. Для любых формул , , справедливы для любого следующие свойства:

1.

2..

3.Если и , то

.

4.

5.

6.

7.

8..

9. .

 

2. Мера информативности и ее свойства

С точки зрения важности информации, сообщенной экспертом, естественно считать, что информативность высказывания тем выше, чем меньше моделей (или мера), на которых оно выполнимо, поэтому введем информативность следующим образом.

Определение5. Пусть - предикат, отражающий знание эксперта, тогда мерой информативности предиката назовем величину

, где 1 -- тождественно истинный предикат.

Теорема2. Для любых формул ,

1.

2.

3. .

4.

5.

6.

7.

8. Если , то

9. Если ,

то

10.

11.

 

3. Асимптотические свойства расстояний

Часто неизвестен точный размер области определения, известно только, что большое. Поэтому имеет смысл изучать асимптотическое поведение расстояния между высказываниями экспертов при устремлении к бесконечности. Зависимость расстояния от дальше будем обозначать через . По поводу асимптотического исследования в этом случае получены следующие результаты.

Теорема3. Если и высказывания экспертов, записанные как предложения языка первого порядка, состоящего только из предикатных символов, тогда

а) сходится к 0 или 1 при

б) Если одно из высказываний и отрицание другого принадлежат некоторой полной непротиворечивой теории (множеству предложений), то

в) Если оба этих высказывания либо их отрицания принадлежат некоторой полной непротиворечивой теории, то

4. Расстояние между деревьями решений и мера информативности

Пусть задан исходный набор переменных с областями значений и , -набор значений переменных для объекта . Пусть -дерево решений, разбивающее множество объектов на образов.

Из определения дерева решений [1] следует, что для любого ; для , и каждое дерево решений дает:

1) Разбиение множества на попарно непересекающиеся подмножества , где , ; , ; (набор переменных, по которому строится каждая ветвь дерева, может быть произвольным);

Замечание: если нескольким путям, ведущим от корня дерева к висячей вершине, соответствуют области соответственно, которые определяют один и тот же образ , то в разбиении .

2) Значения образов (классов) , .

3) Каждому пути от корня дерева к висячей вершине соответствует формула , где каждый предикат определяется заданием множества .

Замечание: если формулы определяют один и тот же образ , то вместо них рассматриваем формулу , которая будет определять образ .

4) Дереву соответствует набор формул .

Пусть -конечное множество деревьев решений, разбивающих множество объектов на образов. И пусть дереву соответствует набор формул , а дереву - .

Замечание: Формулы и определяют один и тот же образ со значением .

Определение6. Расстоянием между деревьями и назовем величину , где

С точки зрения наилучшего разбиения множества будем считать, что информативность дерева решений тем выше, чем больше расстояние между подмножествами разбиения, поэтому введем информативность следующим образом.

Определение7. Пусть - дерево решений, тогда его мерой информативности назовем величину

Теорема4. Для любых деревьев решений и верны свойства:

1.

2. , (1- дерево решений с одним классом в случае ).

3., (имеет смысл только для двух классов).

4. Если = (совпадение деревьев в смысле разбиений и значений образов), то .

5. , (пересечение и объединение деревьев по подмножествам, определяющим один и тот же образ).

6. Если , то .

Работа проделана частично при поддержке гранта РФФИ № 980100673 и программы ‘’Интеграция’’.

1. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука, 1981, 158 с.
1. Викентьев А.А., Коренева Л.Н. Расстояние на высказываниях экспертов.// Сборник научных статей Международной конференции ’’Компьютерный анализ данных и моделирование’’. Минск, 1998. С. 160-166.